
# 最多能走 2 步的时候
def ways_max2(height):
    if height == 0 or height == 1:
        return 1
    
    return ways_max2(height - 1) + ways_max2(height - 2)


# 最多能走 3 步的时候
def ways_max3(height):
    if height == 0 or height == 1:
        return 1
    elif height == 2:
        return 2
    
    return ways_max3(height - 3) + ways_max3(height - 2) + ways_max3(height - 1)

# 最多能走 n 步的时候

def ways(height, max_steps):
    if height == 0 or height == 1:
        return 1

    ways = 0
    for i in range(1, min(height, max_steps) + 1):
        ways += ways(height - i, max_steps)

    return ways

print(ways(3, 3))

# non recursive implementation

def ways_iterative(height, max_steps):
    ways = [0] * (height + 1)
    ways[0] = 1
    ways[1] = 1

    for currHeight in range(2, height + 1):
        i = 1
        steps = 0

        while i <= currHeight and i <= max_steps:
            steps += ways[currHeight - i]
            ++i

        ways.append(steps)
    
    return ways[height]